package LimitedTimeGame.Day_0217;

/**
 * @author zxc
 * @date 2023/02/17 18:01
 **/
/**
 * 题目 ：分割链表
 * 题目详述 ：
 * 给你一个链表的头节点 head 和一个特定值 x ，
 * 请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
 * 你应当 保留 两个分区中每个节点的初始相对位置。
 *
 * 提示：
 * 链表中节点的数目在范围 [0, 200] 内
 * -100 <= Node.val <= 100
 * -200 <= x <= 200
 *
 */
public class Partition02 {
    /**
     * 思路 ：
     * ===》
     * 即，维护两个链表list1 && list2
     * （1）list1链表，保存所有小于x的链表节点;
     * （2）list2链表，保存所有大于等于x的链表节点;
     * （3）即，将list1链表与list2链表进行相互连接;（即，list1的尾节点指向list2的头结点,从而形成一条已经排序好的链表;）
     * @param head
     * @param x
     * @return
     */
    public ListNode partition(ListNode head, int x) {
        ListNode small = new ListNode();
        // smallHead节点，指向维护的small链表的头节点;
        ListNode smallHead = small;
        ListNode large = new ListNode();
        // largeHead节点，指向维护的large链表的头节点;
        ListNode largeHead = large;
        while(head != null){
            if(head.val < x){
                // 即，使的small链表尾节点的next指针指向head节点; && 使得small链表的尾节点切换为 新加入的head节点;
                small.next = head;
                small = head;
            }
            else {
                // 即，使的large链表尾节点的next指针指向head节点; && 使得large链表的尾节点切换为 新加入的head节点;
                large.next = head;
                large = head;
            }
            // 遍历当前链表中的所有节点;
            head = head.next;
        }
        // small链表中尾节点与large链表中头结点相连;
        small.next = largeHead.next;
        // large链表中尾节点的next指针指向null;
        large.next = null;
        return smallHead.next;
    }

    public class ListNode {
        int val;
        ListNode next;
        ListNode() {};
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}
